package 周赛;

import java.util.*;

public class 两个回文子序列长度的最大乘积 {
    public boolean check(String s){
        int len=s.length();
        for (int i = 0; i < s.length()/2; i++) {
            if (s.charAt(i)!=s.charAt(len-1-i))
                return false;
        }
        return true;
    }
    int res=1;
    public int maxProduct(String s) {
           dfs(0,s,"","");
           return res;
    }

    private void dfs(int idx, String s, String a, String b) {
        if (check(a)&& check(b))
            res=Math.max(res,a.length()*b.length());
        if (idx==s.length())
            return;
        dfs(idx+1,s,a+s.charAt(idx),b);
        dfs(idx+1,s,a,b+s.charAt(idx));
        dfs(idx+1,s,a,b);
    }
//    public int maxProduct2(String s) {
//        //找出所有的子序列
//        List<List<Character>> lists = new ArrayList<>();
//        List<Character> list = new ArrayList<>();
//        dfs(lists,list,s,0);
//        return 0;
//    }
//
//    private void dfs(List<List<Character>> lists, List<Character> list, String s, int idx) {
//        lists.add(new ArrayList<>(list));
//        for (int i = idx; i < s.length(); i++) {
//            list.add(s.charAt(i));
//            dfs(lists,list,s,i+1);
//            list.remove(list.size()-1);
//        }
//    }
//
//    public int maxProduct1(String s) {
//        //找两个字符相同的个数
//        Map<Character, Integer> map = new HashMap<>();
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            map.put(c,map.getOrDefault(c,0)+1);
//        }
//        int num=0;
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if (map.containsKey(c)){
//                num+=map.get(c)/2;
//                map.remove(c);
//            }
//        }
//        if (num%2==0){
//            return (num+1)*(num+1);
//        }
//        else
//            return num*(num+2);
//    }
}
